package _11_整理题目._6_模拟设计._区间覆盖问题;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/remove-covered-intervals/
 * https://leetcode-cn.com/problems/remove-covered-intervals/solution/shan-chu-bei-fu-gai-qu-jian-by-leetcode-solution/
 *
 * 给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。
 * 只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。
 * 在完成所有删除操作后，请你返回列表中 剩余区间个数 和 剩余区间。
 *
 *
 */
public class _03_删除被覆盖区间 {

    // 删除重复区间，计算剩余区间数
    public int removeCoveredIntervals(int[][] intervals) {
        Arrays.sort(intervals, (v1, v2) -> {
            if (v1[0] != v2[0]) {
                return v1[0] - v2[0];
            } else {
                return v2[1] - v1[1];
            }
        });

        int n = intervals.length;
        int ans = n;
        int maxRight = intervals[0][1];
        for (int i = 1; i < n; i++) {
            if (intervals[i][1] > maxRight) {
                maxRight = intervals[i][1];
            } else {
                ans--;
            }
        }
        return ans;
    }

    @Test
    public void main() {
        int[][] intervals = {{1,4}, {1,3}, {3,6}, {2,8}};
        System.out.println(removeCoveredIntervals(intervals));

        int[][] result = removeCoveredIntervals2(intervals);
        for (int[] ints : result) {
            System.out.println(Arrays.toString(ints));
        }
    }

    // 删除重复区间，返回剩余区间
    public int[][] removeCoveredIntervals2(int[][] intervals) {
        Arrays.sort(intervals, (v1, v2) -> {
            if (v1[0] != v2[0]) {
                return v1[0] - v2[0];
            } else {
                return v2[1] - v1[1];
            }
        });

        int n = intervals.length;
        List<int[]> ans = new ArrayList<>();
        ans.add(intervals[0]);
        int maxRight = intervals[0][1];
        for (int i = 1; i < n; i++) {
            if (intervals[i][1] > maxRight) {
                maxRight = intervals[i][1];
                ans.add(intervals[i]);
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }
}
